/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#include <cassert>
#include "PartialOrder.h"
#include "AlgoGraph.h"

double dmax(double a, double b)
{
    return a>b?a:b;
}

    PartialOrder::PartialOrder(Matrix m)
: _pSubMatrix(m), _pMatrix(&_pSubMatrix), _dEpsilon(0), _constructBeetweness(true)
{
    init();
}

    PartialOrder::PartialOrder ( Matrix *m )
: _pMatrix(m), _dEpsilon(0), _constructBeetweness(true)
{
    init();
}

void PartialOrder::init()
{
    _vvpInterval.resize( _pMatrix->getSize() );
    _vspInterval.resize( _pMatrix->getSize() );
    _vsGraphe.resize( _pMatrix->getSize() );
    _vsNoGraphe.resize( _pMatrix->getSize() );

    for (unsigned int i = 0; i < _pMatrix->getSize(); i++)
    {
        _vvpInterval[i].resize( _pMatrix->getSize() );
        for (unsigned int j = i; j < _vvpInterval[i].size(); j++)
            _vvpInterval[i][j] = new Interval(i, j);
    }

    for (unsigned int i = 0; i < _pMatrix->getSize(); i++)
        for (unsigned int j = 0; j < i; j++)
            _vvpInterval[i][j] = _vvpInterval[j][i];
}

void PartialOrder::update( std::pair<unsigned int, unsigned int> p, bool allRules, bool fast )
{
    _spToUpdate.erase( p );

    if ( allRules )
    {
        if(!fast)
        {
            PO1( p.first, p.second );
            PO2( p.first, p.second );
        }
        else
            PO1_fast( p.first, p.second );
    }

    PO3_4_5_6( p.first, p.second );
}


void PartialOrder::update( bool allRules, bool fast)
{
    assert( _pMatrix!=NULL || !"Matrix no init" );
    while( _spToUpdate.size() > 0 )
        update( *(_spToUpdate.begin()), allRules, fast );
}

void PartialOrder::setOrderForTwoArbitraryElements(bool forceSetSecondeElements)
{
    setOrientation(_pMatrix->getSize()-2, _pMatrix->getSize()-1);

    for (unsigned int i = 0; i < _pMatrix->getSize()-2; i++)
    {
        setOrientation(i, _pMatrix->getSize()-1);
        setOrientation(_pMatrix->getSize()-2, i);
    }

    if( forceSetSecondeElements )
    {
        for (unsigned int i = 0; i < _vvpInterval.size(); i++)
        {
            for (unsigned int j = 0; j < _vvpInterval[i].size(); j++)
            {
                if( (i==(_pMatrix->getSize()-2)) && (j==(_pMatrix->getSize()-1)) )
                {
                    setOrientation(0 , 1);
                    return;
                }

                if( _vvpInterval[i][j]->getList().size() > 0 )
                {
                    setOrientation(i, j);
                    return;
                }
            }
        }
    }
}

void PartialOrder::reinit( double epsilon, bool fast )
{
    _spToUpdate.clear();

    for (unsigned int i = 0; i < _vvpInterval.size(); i++)
    {
        _vsGraphe[i].clear();
        _vsNoGraphe[i].clear();
        _vspInterval[i].clear();
        for (unsigned int j = i+1; j < _vvpInterval[i].size(); j++)
            _vvpInterval[i][j]->reinit();
    }

    _dEpsilon = epsilon;

    if(!fast)
    {
        for (unsigned int i = 0; i < _vvpInterval.size(); i++)
            for (unsigned int j = i+1; j < _vvpInterval[i].size(); j++)
                for (unsigned int k = 0; k < _vvpInterval.size(); k++)
                    if( _pMatrix->get(i, j) > (dmax( _pMatrix->get(i, k), _pMatrix->get(k, j) ) + 2*_dEpsilon ))
                        addElementToB(_vvpInterval[i][j], k);

        // Closing B by adding all triplets of the form (x,u,y) satisfing the B1-4 rules
        for ( unsigned int i = 0; i < _pMatrix->getSize(); ++i )
            for ( unsigned int j = 0; j < _vvpInterval.size(); ++j )
                for ( unsigned int k = j+1; k < _vvpInterval[j].size(); ++k )
                    if ( (j != i) && (k != i) &&
                            ( B1(i, _vvpInterval[j][k])
                              || B2(i, _vvpInterval[j][k])
                              || B3(i, _vvpInterval[j][k])
                              || B4(i, _vvpInterval[j][k]) ) )
                    {
                        continue;
                    }
    }
}


PartialOrder::~PartialOrder ()
{
    for (unsigned int i = 0; i < _vvpInterval.size(); i++)
        for (unsigned int j = i; j < _vvpInterval[i].size(); j++)
            delete _vvpInterval[i][j];
}

void PartialOrder::setOrientation(unsigned int a, unsigned int b)
{
    if( _vsGraphe[a].count(b) == 0)
    {
        _vsGraphe[a].insert(b);
        _vsNoGraphe[b].insert(a);
        _spToUpdate.insert( std::pair<unsigned int, unsigned int>(a, b) );
    }
}


bool PartialOrder::B1( unsigned int u, Interval* interval )
{
    std::set<unsigned int> &elementsLit = interval->getList();
    for ( std::set<unsigned int>::iterator i = elementsLit.begin(); i != elementsLit.end(); ++i )
        if ( (*i != u) &&
                (_vvpInterval[interval->getX()][*i]->contains(u)
                 || _vvpInterval[*i][interval->getY()]->contains(u) ) )
        {
            addElementToB(interval , u);
            return true;
        }
    return false;
}

bool PartialOrder::B2( unsigned int /*u*/, Interval* /*interval*/ )
{
    return false;
}

bool PartialOrder::B3( unsigned int /*u*/, Interval* /*interval*/ )
{
    return false;
}

bool PartialOrder::B4( unsigned int /*u*/, Interval* /*interval*/ )
{
    return false;
}


void PartialOrder::PO1_fast( unsigned int x, unsigned int y )
{
    for ( unsigned int i = 0; i < _pMatrix->getSize(); ++i )
        if ( _pMatrix->get(x, y) > (dmax( _pMatrix->get(x, i), _pMatrix->get(i, y) ) + 2*_dEpsilon ) )
        {	
            setOrientation(x, i);
            setOrientation(i, y);
        }
}

void PartialOrder::PO1( unsigned int x, unsigned int y )
{
    for (std::set<unsigned int>::iterator it = getInterval(x, y)->getList().begin(); it != getInterval(x, y)->getList().end(); ++it)
    {
        setOrientation(x, *it);
        setOrientation(*it, y);
    }
}

void PartialOrder::PO2( unsigned int x, unsigned int y )
{
    for (std::set<Interval*>::iterator it = _vspInterval[x].begin(); it != _vspInterval[x].end(); ++it)
    {
        if( ((*it)->getX() == y) )
        {
            setOrientation((*it)->getY(), x);
            setOrientation((*it)->getY(), y);
        }else if( (*it)->getY() == y )
        {
            setOrientation((*it)->getX(), x);
            setOrientation((*it)->getX(), y);
        }
    }

    for (std::set<Interval*>::iterator it = _vspInterval[y].begin(); it != _vspInterval[y].end(); ++it)
    {
        if( ((*it)->getX() == x) )
        {
            setOrientation(x, (*it)->getY());
            setOrientation(y, (*it)->getY());
        }else if( (*it)->getY() == x )
        {
            setOrientation(x, (*it)->getX());
            setOrientation(y, (*it)->getX());
        }
    }
}

void PartialOrder::PO3_4_5_6( unsigned int x, unsigned int y )
{
    for (unsigned int z = 0; z < _pMatrix->getSize(); z++)
        if( _pMatrix->get(x, z) > (_pMatrix->get(y, z) + 2*_dEpsilon) )
        {
            setOrientation(x, z);
            if( _pMatrix->get(x, z) > (_pMatrix->get(x, y) + 2*_dEpsilon) )
                setOrientation(y, z);
        }
        else if( _pMatrix->get(y, z) > (_pMatrix->get(x, z) + 2*_dEpsilon) )
        {
            setOrientation(z, y);
            if( _pMatrix->get(x, y) > (_pMatrix->get(z, y) + 2*_dEpsilon) )
                setOrientation(x, z);
        }
}


void PartialOrder::addElementToB(Interval *interval, int u)
{
    interval->add(u);
    _vspInterval[u].insert( interval );
}

Interval* PartialOrder::getInterval(unsigned i, unsigned j)
{
    if(i<j)
        return _vvpInterval[i][j];
    else
        return _vvpInterval[j][i];
}


bool PartialOrder::topologicalSorting()
{
    std::set<unsigned int> S;
    for (unsigned int i = 0; i < _vsGraphe.size(); i++)
        S.insert(i);

    return AlgoGraph::topologicalSorting( _vsGraphe, S, _vTopologicalSorting );
}

std::vector< std::set<unsigned int> >& PartialOrder::getGraph()
{
    return _vsGraphe;
}


std::ostream& operator << (std::ostream& os, const PartialOrder& o)
{
    os << std::endl;
    for (unsigned int i = 0; i < o._vsGraphe.size(); i++)
    {
        os << i << " <= ";
        for (std::set<unsigned int>::iterator it = o._vsGraphe[i].begin(); it != o._vsGraphe[i].end(); ++it)
            os << *it << ", ";
        os << std::endl;
    }
    return os;
}

void PartialOrder::setConstructBeetweness( bool val )
{
    _constructBeetweness = val;
}

bool PartialOrder::constructBeetweness()
{
    return _constructBeetweness;
}

Matrix *PartialOrder::getMatrix()
{
    return _pMatrix;
}

